import java.util.Arrays;
import java.util.Comparator;

public class SortAlgorithm {
    public static void main(String[] args) {
       int[] nums1 = { 1,3,4,2,5 ,3,3,6};
       quickSort2(nums1,0,6);
      // System.out.println( process(nums1,0,4));
        System.out.println( Arrays.toString(nums1));
    }




    /*
    冒泡排序===============================================================================================
     */
    public static void bubblrSort(int[] nums) {
        for(int i = 0;i<nums.length-1;i++){
            for(int j = 0;j<nums.length-1-i;j++){
                if(nums[j]>nums[j+1]){
                    int temp = nums[j];
                    nums[j]= nums[j+1];
                    nums[j+1]= temp;
                }
            }
        }
    }
    /*
    插入排序===============================================================================================

     */
    public static void insertionSort(int[] nums) {
        for(int i= 1;i<nums.length;i++){
            int temp = nums[i];
            int j = i-1;
            while(j>=0&&nums[j]>temp){
                nums[j+1]=nums[j];
                j--;
            }
            nums[j+1]=temp;
        }
    }
    /*
    选择排序===============================================================================================
     */
    public static void selectionSort(int[] nums) {
        for(int i= 0;i<nums.length-1;i++){
            int minIndex = i;
            for(int j = i +1;j<nums.length;j++){
                if(nums[j]<nums[minIndex]){
                    minIndex=j;
                }
            }
            int temp = nums[minIndex];
            nums[minIndex]=nums[i];
            nums[i]=temp;
        }
    }
    /*
    快速排序===============================================================================================
     */
    public static void quickSort(int[] nums,int low,int high) {
        if(low<high){
            int pivot = partition(nums,low,high);
            quickSort(nums,low,pivot-1);
            quickSort(nums,pivot+1,high);
        }
    }
    public static int partition(int[] nums, int low, int high) {
        int pivot = nums[low];
        while (low < high) {
            while(low<high&&nums[high]>=pivot) high--;
            nums[low] = nums[high];
            while(low<high&&nums[low]<=pivot) low++;
            nums[high] = nums[low];
        }
        nums[low] = pivot;
        return low;
    }

    /*
    基于荷兰国旗问题的快速排序
    可以一次处理数组中值相同的一批数
     */
    public static int[] neitherLandFlag(int[] nums,int L,int R){
        if(L==R){
            return new int[] {L,R};
        }
        int less = L-1;
        int more = R;
        int index = L;
        while (index<more){
            if(nums[index]==nums[R]){
                index++;
            }
            if(nums[index]<nums[R]){
                swap(nums,index++,++less);
            }else{
                swap(nums,index,--more);
            }
        }
        swap(nums,more,R);
        return new int[] {less+1,more};
    }
    public static void quickSort2(int[] nums, int L, int R){
        if(L>=R) return;
        int[] equalArea = neitherLandFlag(nums,L,R);
        quickSort2(nums,L,equalArea[0]-1);
        quickSort2(nums,equalArea[1]+1,R);
    }
    public static void swap(int[] nums, int i, int i1) {
        int temp =nums[i];
        nums[i] = nums[i1];
        nums[i1] = temp;
    }

    /*
    计数排序===============================================================================================
     */
    public static void coutingSort(int[] nums) {
        int[] temp = new int[4];
        for(int i = 0;i<nums.length;i++){
            temp[nums[i]-1]++;
        }
        int[] newNums = new int[nums.length];
        int index = 0;
        for(int i= 0;i<temp.length;i++){
            for(int j=0;j<temp[i];j++){
                newNums[index++]=i+1;
            }
        }
        System.out.println(Arrays.toString(newNums));
    }

    /*
    归并排序===============================================================================================
     */
    public static void mergeSort(int[] nums,int r,int l){
        if(r==l) return;
        int mid = r+((l-r)>>1);
        mergeSort(nums,r,mid);
        mergeSort(nums,mid+1,l);
        merge(nums,r,mid,l);
    }
    private static void merge(int[] nums, int r, int mid,int l) {
        int[] nums2 =new int[l-r+1];
        int i =0;
        int temp1 = r,temp2 = mid+1;
        while (temp1<=mid&&temp2<=l){
            nums2[i++] = nums[temp1]<nums[temp2]?nums[temp1++]:nums[temp2++];
        }
        while (temp1<=mid){
            nums2[i++]=nums[temp1++];
        }
        while (temp2<=l){
            nums2[i++]=nums[temp2++];
        }
       for(int j =0;j<nums2.length;j++){
           nums[r+j] = nums2[j];
       }
    }
    /*
    非递归实现的归并排序
     */
    public static void mergeSort2(int[] nums){
        if(nums==null||nums.length<2){
            return;
        }
        int n = nums.length;
        //当前的归并规模，从1开始，每次乘2
        int mergeSize = 1;
        while (mergeSize<n){
            //l为左组的左边界
            int l =0;
            while (l<n){
                //m为右组的左边界
                int m = l+mergeSize-1;
                //右组不存在时直接退出
                if(m>=n) break;
                //r是右组的右边界
                int r = Math.min(m+mergeSize,n-1);
                merge(nums,l,m,r);
                l=r+1;
            }
            //防止mergesize溢出
            if(mergeSize>(n<<1)){
                break;
            }
            mergeSize<<=1;
        }

    }

    /*
    归并排序的应用：
                在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数
                例子，[13425]
                1左边比1小的数：没有
                3左边比3小的数：1
                4左边比4小的数：1，3
                2左边比2小的数：1
                5左边比5小的数．1、3、4`2
                所以数组的小和为1+1+3+1+1+3+4+2=16
     */
    public static int process(int[] nums , int l,int r){
        if(l==r) return 0;
        int mid = l +((r-l)>>1);
        return process(nums,l,mid)+
                process(nums,mid+1,r)+
                merge2(nums,l,mid,r);
    }

    private static int merge2(int[] nums, int l, int mid, int r) {
        int[] nums2 =new int[r-l+1];
        int i =0;
        int temp1 = l,temp2 = mid+1;
        int res = 0;
        while (temp1<=mid&&temp2<=r){
            res+=nums[temp1]<nums[temp2]?(r-temp2+1)*nums[temp1]:0;
            nums2[i++] = nums[temp1]<nums[temp2]?nums[temp1++]:nums[temp2++];
        }
        while (temp1<=mid){
            nums2[i++]=nums[temp1++];
        }
        while (temp2<=r){
            nums2[i++]=nums[temp2++];
        }
        for(int j =0;j<nums2.length;j++){
            nums[l+j] = nums2[j];
        }
        return res;
    }
}